/*
 * @lc app=leetcode.cn id=153 lang=cpp
 *
 * [153] 寻找旋转排序数组中的最小值
 */

// @lc code=start
class Solution {
public:
    int findMin(vector<int>& nums) {
        //二分法
        //左边区间不满足nums[mid] < nums[0]
        //右边区间满足nums[mid] < nums[0]

        //未翻转的特殊情况
        //二分模板时
        //把右边当成check的条件，此时 r = mid; mid = l + r >> 1
        if(nums[nums.size() - 1] > nums[0]) return nums[0];

        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }

        return nums[l];
    }
};
// @lc code=end

